#include <vector>

using namespace std;

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> fibonacci = {1, 1};
        for (int i = 1; ; i++) {
            int num = fibonacci[i] + fibonacci[i - 1];
            if (num > k) {
                break;
            }
            fibonacci.emplace_back(num);
        }
        int ans = 0;
        int i = fibonacci.size() - 1;
        while (k > 0) {
            ans += k / fibonacci[i];
            k %= fibonacci[i];
            i--;
        }
        return ans;
    }
};